/*
Brick And Blast, a crossplatform breakout game.
 Copyright (C) 2008-2010 Julien CLEMENT (andematunum@gmail.com)
 
 This program is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 2
 of the License, or (at your option) any later version.
 
 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 GNU General Public License for more details.
 
 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 

*/

#ifndef _ObjectGrid_h_
#define _ObjectGrid_h_

/**
* file   ObjectGrid.h
* date   Mar 29 déc 2009 14:04:17 CET
* brief  An efficient way to optimize collisions
*        is to segment the objects in a grid so
*        that the tests are limited to the objects
*        belonging to the same cell of the grid.
*        It is maybe slower than a quadtree when
*        the objects are grouped, but simpler to maintain.
*/

#include "SDL.h"
#include <set>
#include <iostream>
using namespace std;

#define GRID_CELL_W (1024)
#define GRID_CELL_H (768)
//#define GRID_W ((int)(992. / (double)GRID_CELL_W) + 1)
//#define GRID_H ((int)(656. / (double)GRID_CELL_H) + 1)
#define GRID_W ((992 / GRID_CELL_W) + 1)
#define GRID_H ((656 / GRID_CELL_H) + 1)

class GameObject;
typedef set<GameObject*> Cell;

class ObjectGrid {
public:
  ObjectGrid () {
  }
  /** Set the grid margin, which corresponds to the
    * coordinates of the grid origin (top left) in the pixel space (screen). */
  void set_margin (int margin_left, int margin_top) {
    margin_left_ = margin_left;
    margin_top_  = margin_top;
  }
  /** Add a new object in the grid. */
  void add_object (GameObject* object);
  /** Remove an object from the grid. */
  void remove_object (GameObject* object);
  /** Given an object, examine its configuration at the next position:
    * Get the list of cells it will belong to
    * Get the list of objects in each of those cells.
    * The list of cells will be used to update the object later.
    *
    * \sa update_object
    * \sa get_intersected_cells
    */
  void get_neighborhood (set<GameObject*>& neighbors, set< Cell* >& cells,
                         GameObject* object);
  /** Update an object after it moved.
    * Removes the object from its current cells, and add
    * it to the new cells it belongs to, given by \p cells.
    */
  void update_object (GameObject* object, set< Cell* >& cells);
  /** Check if an object can be placed at the given position.
    * Said differently, check whether there is an object at the specified position.*/
  bool free_area (SDL_Rect& rect) {
    return true;
  }

private:
  /** Get the cell at grid position x,y */
  Cell* get_cell (SDL_Point& grid_xy) {
    return &cells_[grid_xy.x][grid_xy.y];
  }
  /** Get the cells intersected by the given rectangle.
    * Up to 4 is supported. */
  void get_intersected_cells (set< Cell* >& cells, const SDL_Rect& rect);
  /** Convert a point in pixel space into a point in grid space. */
  void pixel_2_grid (SDL_Point& grid_xy, SDL_Point& pixel_xy) {
    grid_xy.x = static_cast<int>(((double)(pixel_xy.x - margin_left_)) / (double)GRID_CELL_W);
    grid_xy.y = static_cast<int>(((double)(pixel_xy.y - margin_top_))  / (double)GRID_CELL_H);
  }

private:
  /** The grid may not fit exactly with the top-left screen origin.
    * So, a margin must be explicitly defined. */
  int margin_left_;
  int margin_top_;
  Cell cells_[GRID_W][GRID_H];
};

#endif

